home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / snip9_91.arc / APPROX.C < prev    next >
C/C++ Source or Header  |  1991-09-17  |  5KB  |  161 lines
  1. /***************************************************************
  2.  *
  3.  * Fuzzy string searching subroutines
  4.  *
  5.  * Author:    John Rex
  6.  * Date:      August, 1988
  7.  * References: (1) Computer Algorithms, by Sara Baase
  8.  *                 Addison-Wesley, 1988, pp 242-4.
  9.  *             (2) Hall PAV, Dowling GR: "Approximate string matching",
  10.  *                 ACM Computing Surveys, 12:381-402, 1980.
  11.  *
  12.  * Verified on Datalite, DeSmet, Ecosoft, Lattice, MetaWare, MSC, Turbo, Watcom
  13.  *
  14.  * Compile time preprocessor switches:
  15.  *      DEBUG - if defined, include test driver
  16.  *
  17.  * Usage:
  18.  *
  19.  *   char *pattern, *text;  - search for pattern in text
  20.  *   int degree;        - degree of allowed mismatch
  21.  *   char *start, *end;
  22.  *   int howclose;
  23.  *
  24.  *   void App_init(pattern, text, degree);   - setup routine
  25.  *   void App_next(&start, &end, &howclose); - find next match
  26.  *
  27.  *   - searching is done when App_next() returns start==NULL
  28.  *
  29.  **************************************************************/
  30.  
  31. #define DEBUG 1
  32.  
  33. #include <stdio.h>
  34.  
  35. /* local, static data */
  36.  
  37. static char *Text, *Pattern; /* pointers to search strings */
  38. static int Textloc;         /* current search position in Text */
  39. static int Plen;         /* length of Pattern */
  40. static int Degree;         /* max degree of allowed mismatch */
  41. static int *Ldiff, *Rdiff;   /* dynamic difference arrays */
  42. static int *Loff,  *Roff;    /* used to calculate start of match */
  43.  
  44. void App_init(pattern, text, degree)
  45. char *pattern, *text;
  46. int degree;
  47. {
  48.     void *malloc();
  49.     int strlen(), i;
  50.  
  51.     /* save parameters */
  52.     Text = text;
  53.     Pattern = pattern;
  54.     Degree = degree;
  55.  
  56.     /* initialize */
  57.     Plen = strlen(pattern);
  58.     Ldiff  = (int *) malloc(sizeof(int) * (Plen + 1) * 4);
  59.     Rdiff  = Ldiff + Plen + 1;
  60.     Loff   = Rdiff + Plen + 1;
  61.     Roff   = Loff +  Plen + 1;
  62.     for (i = 0; i <= Plen; i++) {
  63.         Rdiff[i] = i;   /* initial values for right-hand column */
  64.         Roff[i]  = 1;
  65.     }
  66.  
  67.     Textloc = -1; /* current offset into Text */
  68. }
  69.  
  70. void App_next(start, end, howclose)
  71. char **start, **end;
  72. int *howclose;
  73. {
  74.     int *temp, a, b, c, i;
  75.     void free();
  76.  
  77.     *start = NULL;
  78.     while (*start == NULL) { /* start computing columns */
  79.         if (Text[++Textloc] == '\0') /* out of text to search! */
  80.             break;
  81.  
  82.         temp = Rdiff;   /* move right-hand column to left ... */
  83.         Rdiff = Ldiff;  /* ... so that we can compute new ... */
  84.         Ldiff = temp;   /* ... right-hand column */
  85.         Rdiff[0] = 0;    /* top (boundary) row */
  86.  
  87.         temp = Roff;    /* and swap offset arrays, too */
  88.         Roff = Loff;
  89.         Loff = temp;
  90.         Roff[1] = 0;
  91.  
  92.         for (i = 0; i < Plen; i++) { /* run through pattern */
  93.             /* compute a, b, & c as the three adjacent cells ... */
  94.             if (Pattern[i] == Text[Textloc])
  95.                 a = Ldiff[i];
  96.             else
  97.                 a = Ldiff[i] + 1;
  98.             b = Ldiff[i+1] + 1;
  99.             c = Rdiff[i] + 1;
  100.  
  101.             /* ... now pick minimum ... */
  102.             if (b < a)
  103.                 a = b;
  104.             if (c < a)
  105.                 a = c;
  106.  
  107.             /* ... and store */
  108.             Rdiff[i+1] = a;
  109.         }
  110.  
  111.         /* now update offset array */
  112.         /* the values in the offset arrays are added to the
  113.            current location to determine the beginning of the
  114.            mismatched substring. (see text for details) */
  115.         if (Plen > 1) for (i=2; i<=Plen; i++) {
  116.             if (Ldiff[i-1] < Rdiff[i])
  117.                 Roff[i] = Loff[i-1] - 1;
  118.             else if (Rdiff[i-1] < Rdiff[i])
  119.                 Roff[i] = Roff[i-1];
  120.             else if (Ldiff[i] < Rdiff[i])
  121.                 Roff[i] = Loff[i] - 1;
  122.             else /* Ldiff[i-1] == Rdiff[i] */
  123.                 Roff[i] = Loff[i-1] - 1;
  124.         }
  125.  
  126.         /* now, do we have an approximate match? */
  127.         if (Rdiff[Plen] <= Degree) { /* indeed so! */
  128.             *end = Text + Textloc;
  129.             *start = *end + Roff[Plen];
  130.             *howclose = Rdiff[Plen];
  131.         }
  132.     }
  133.  
  134.     if (start == NULL) /* all done - free dynamic arrays */
  135.         free(Ldiff);
  136. }
  137.  
  138. #ifdef DEBUG
  139. void main(argc, argv)
  140. int argc;
  141. char **argv;
  142. {
  143.     int atoi();
  144.     char *begin, *end;
  145.     int howclose;
  146.     void exit();
  147.  
  148.     if (argc != 4) {
  149.         puts("Usage is: approx pattern text degree\n");
  150.         exit(0);
  151.     }
  152.  
  153.     App_init(argv[1], argv[2], atoi(argv[3]));
  154.     App_next(&begin, &end, &howclose);
  155.     while (begin != NULL) {
  156.         printf("Degree %d: %.*s\n", howclose, end-begin+1, begin);
  157.         App_next(&begin, &end, &howclose);
  158.     }
  159. }
  160. #endif
  161.